#include <stdio.h>
#include <stdlib.h>

/*bool类型的定义*/
#define true 1
#define false 0
typedef unsigned char bool;
/*链表节点结构体*/
typedef struct LNode {
    int data;
    struct LNode* next;
} LNode;
typedef LNode* LinkList; // 对链表节点的指针重命名为LinkList,可读性更好

/*===================带头结点的方式==================*/
/*初始化*/
bool InitList_with_head(LinkList* L) {
    *L = (LinkList)malloc(sizeof(LNode));
    if (*L == NULL) {
        return false;
    }
    (*L)->next = NULL;
    return true;
}
/*插入,通过位序*/
bool InsertListByIndex_with_head(LinkList* L, int i, int e){
    if(i<1){
        return false;
    }
    LNode *p;   //指针指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = *L;     //L指向头结点,头结点是第0个节点
    while(p!=NULL&&j<i-1){  //循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if(p == NULL){  //i值不合法
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));  //申请了新的节点
    s->data = e;
    s->next = p->next;  //将新的节点的下一个节点设置为头结点的下一个地址
    p->next = s;    //将节点s连到p之后,也就是头结点之后
    return true;    //插入成功
}
/*==========================不带头节点============================*/
/*初始化*/
bool InitList_without_head(LinkList *L){
    *L = NULL;
    return true;
}
/*判空*/
bool Empty_without_head(LinkList L){
	if(L == NULL){
		return true;
	}else{
		return false;
	}
}
/*插入,通过位序*/
bool InsertListByIndex_without_head(LinkList* L, int i, int e){
    if(i<1){
        return false;
    }
    //处理插入第一个节点的情况
    if(i == 1){
        LNode * s = (LNode *)malloc(sizeof(LNode));
        if (s == NULL) return false;  // 检查malloc是否成功
        s->data = e;
        s->next = *L;
        *L = s;
        return true;
    }

    LNode *p;   //指针指向当前扫描到的节点
    int j = 1;  //当前p指向的是第几个节点
    p = *L;     //L指向头结点,头结点是第0个节点
    while(p!=NULL&&j<i-1){  //循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if(p == NULL){  //i值不合法
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));  //申请了新的节点
    s->data = e;
    s->next = p->next;  //将新的节点的下一个节点设置为头结点的下一个地址
    p->next = s;    //将节点s连到p之后,也就是头结点之后
    return true;    //插入成功
}
int main() {
    LinkList L1, L2;
    
    // 测试带头结点链表
    InitList_with_head(&L1);
    bool b1 = InsertListByIndex_with_head(&L1, 1, 10);
    bool b2 = InsertListByIndex_with_head(&L1, 2, 20);
    printf("带头节点:1-%d;2-%d\n",b1,b2);
    // 测试不带头结点链表
    InitList_without_head(&L2);
    bool b3 = InsertListByIndex_without_head(&L2, 1, 100);  // 插入第一个节点
    bool b4 = InsertListByIndex_without_head(&L2, 2, 200);  // 插入第二个节点
    printf("带头节点:1-%d;2-%d\n",b3,b4);
    return 0;
}